#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;


class Solution1 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[0] = 1, g[n - 1] = 1;
        for (int i = 1; i < n; i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--)
        {
            g[i] = g[i + 1] * nums[i + 1];
        }
        vector<int> answer(n);
        for (int i = 0; i < n; i++)
        {
            answer[i] = f[i] * g[i];
        }

        return answer;
    }
    
};
#include<unordered_map>
class Solution2 {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, count = 0;
        unordered_map<int,int> hash;
        hash[0] = 1;
        for (auto e : nums)
        {
            sum += e;
            if (hash.count(sum - k))
            {
                count += hash[sum-k];
            }
            hash[sum]++;
        }
        return count;
    }
};

class Solution3 {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0, count = 0;
        unordered_map<int, int> hash;
        hash[0 % k] = 1;
        for (auto e : nums)
        {
            sum += e;
            int r = (sum % k + k) % k;
            if (hash.count(r))
            {
                count += hash[r];
            }
            hash[r]++;
        }
        return count;
    }
};

#include<algorithm>
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum = 0, n = nums.size();
        int ret = 0;
        unordered_map<int, int> hash;
        hash[0] = -1;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 0) sum += -1;
            else sum += nums[i];
            if (hash.count(sum))
            {
                ret = max(ret, i - hash[sum]);
            }
            else
            hash[sum] = i;
        }
       
        return ret;
        
    }
};
#include<vector>
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int x1, y1, x2, y2;
                x1 = max(0, i - k) + 1;
                y1 = max(0, j - k) + 1;
                x2 = min(m - 1, i + k) + 1;
                y2 = min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;

    }
};
int main()
{
    vector<int> nums = { 0,1,0,1 };
    Solution s;
    /*s.subarraySum(nums, 0);
    int count = s.subarraysDivByK(nums, 5);
    cout << count << endl;
    cout << s.findMaxLength(nums);*/
    return 0;
}